雖然單看各位元運算子好像不難，實際應用在題目上還是很有挑戰。本篇透過 Leetcode 第 371 題、也是 Blind 75 的其中一題：Sum of Two Integers　來看位元運算子的使用組合。

Sum of Two Integers

題目敘述為 Given two integers a and b, return the sum of the two integers without using the operators + and -.，也就是不用 + 跟 - 完成兩整數相加。

不用 + 跟 - 要完成加法（跟減法）的運算，就是位元運算上場時機，先來觀察加法應該有什麼性質。

用 XOR 代替加法運算

如果把兩個二進制的數相加，會得到什麼結果？

假設 a = 10、b = 12，轉換成二進制為 a = 1010、b = 1100，兩者相加應為：

   1010
 + 1100
 -------
  10110

先不要管首位兩個 1 相加出現進位的情況，直接看剩下四位數，正好有個規律：

• 1 + 1 得 0
• 0 + 1 得 1
• 1 + 0 得 1
• 0 + 0 得 0

兩者相同為 0、兩者相異為 1，這不就是 XOR 在做的事情嗎？因此，可以用 XOR 取代加法。

進位的處理

但如果像首位遇到兩個 1 相加得要進位，該怎麼辦？

會進位的只有一種組合，就是上下位元皆為 1，因此要找出位元運算子可以追蹤兩個 1 的組合如下：

• 1 + 1 得 1
• 0 + 1 得 0
• 1 + 0 得 0
• 0 + 0 得 0

這不就是 AND 在做的事情？但進位的 1 不會待在上下皆為 1 的位數，而是會往左移一位，因此做完 AND 後還要左移一位。

以上述範例而言，兩數做完 AND 結果如下：

   1010
 & 1100
 -------
   1000

結果是 1000，但要左移一位，變 10000，別忘了還有剛剛做的 XOR 運算，要把結果加回來：

    0110 <- XOR 運算結果
 + 10000 <- AND 之後左移一位
 -------

這兩者相加其實又代表一次 XOR 運算：

    0110
 ^ 10000
 -------
   10110

那如果再把兩者做一次 AND 追蹤進位呢？

    0110
 & 10000
 -------
   00000

沒有任何地方要進位，因此答案就是 10110，即十進制的 22。

步驟整理

首先，XOR 兩數得 ①。

若要處理進位，進位處為 AND 兩數後，再左移一位得 ②。

把 ① 跟 ② 兩者相加即為兩數加總結果。

但把 ① 跟 ② 相加又要做 XOR 跟進位，因此持續這樣的步驟至不用進位、也就是兩數做 AND 後，結果全為 0 為止。

C++程式碼

依照以上思路，程式碼將寫成：

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            a = a ^ b;         // 先做 a ^ b 取代加法
            b = (a & b) << 1;  // 處理進位
            // 更新後的 a 跟 b 要相加
            // 相當於再跑一次迴圈內容
        }
        return a;
    }
};

但這樣的寫法將導致 b = (a & b) << 1 的 a 是經過 a = a ^ b 運算後的新 a，但其實 b = (a & b) << 1 要的是原本的舊 a，因此要改成：

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;  // 確保這裡的 a 沒有被 a = a ^ b 改到
            a = a ^ b;
            b = carry;                 // 取代原本的 b = (a & b) << 1
        }
        return a;
    }
};

這就是本題答案，時間複雜度與空間複雜度都是 O(1)。

為了避免左移引發溢位，最好也把 carry 改型別成 unsigned int：

int carry = (unsigned int)(a & b) << 1;

參考資料

1. Sum of Two Integers - Leetcode 371 - Java